package com.xaicode.learn.ads.linkedlist;

import lombok.Getter;
import lombok.Setter;
import lombok.ToString;
import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

/**
 * sorted single linked list order by node number
 *
 * @author Locker xaicode@sina.com
 */
@Slf4j
public class SortedSingleLinkedList {

    public static void main(String[] args) {
        SLL sll = new SLL();
        Node node1 = new Node(1, "k1", "v1");
        Node node2 = new Node(2, "k2", "v2");
        Node node3 = new Node(3, "k3", "v3");
        Node node4 = new Node(4, "k4", "v4");
        sll.add(node2);
        sll.add(node4);
        sll.add(node3);
        sll.add(node1);
//        log.info("current list size is " + sll.size());
//        sll.list();
//        log.info(sll.lastNode(3).toString());
//        log.info(sll.reverse().list());
//        sll.reverse().list();
        sll.reversePrintByStack();

//        Node node5 = new Node(4, "k5", "v5");
//        Node node6 = new Node(6, "k6", "v6");
//        sll.update(node5);
//        sll.update(node6);
//        sll.list();

//        sll.remove(4);
//        log.info("current list size is " + sll.size());
//        sll.list();
//        sll.remove(7);

    }

    /**
     * single linked list
     */
    static class SLL {
        /**
         * all nodes data
         */
        private Node nodes = new Node();

        /**
         * sorted add
         */
        public void add(Node targetNode) {
            Node temp = nodes;
            // whether targetNode.no exists or not
            boolean positionExist = false;
            // find the previous node of the specified node
            while (temp.next != null) {
                // compare with node number.
                // the previous node.no is less than targetNode.no and the next node.no is greater than that
                if (temp.next.no > targetNode.no) {
                    break;
                } else if (temp.next.no.equals(targetNode.no)) {
                    positionExist = true;
                    break;
                }
                temp = temp.next;
            }

            if (positionExist) {
                log.error("target node number {} exist", targetNode.no);
            } else {
                targetNode.next = temp.next;
                temp.next = targetNode;
            }
        }

        /**
         * update node by number
         */
        public void update(Node newNode) {
            Node temp = nodes.next;
            // whether newNode.no found
            boolean positionFound = false;
            while (temp != null) {
                if (temp.no.equals(newNode.no)) {
                    positionFound = true;
                    break;
                }
                temp = temp.next;
            }

            if (positionFound) {
                temp.key = newNode.key;
                temp.val = newNode.val;
            } else {
                log.info("target node number {} is not existed", newNode.no);
            }
        }

        /**
         * remove selected node
         */
        public void remove(int number) {
            Node temp = nodes;
            // whether select node found
            boolean positionFound = false;
            while (temp.next != null) {
                if (temp.next.no == number) {
                    positionFound = true;
                    break;
                }
                temp = temp.next;
            }

            if (positionFound) {
                temp.next = temp.next.next;
            } else {
                log.info("target node number {} is not existed", number);
            }
        }

        /**
         * list size.
         * If this list has head node, then remove it before count.
         */
        public int size() {
            if (nodes.next == null) {
                return 0;
            }

            int size = 0;
            Node temp = nodes.next;
            while (temp != null) {
                size++;
                temp = temp.next;
            }
            return size;
        }

        /**
         * find the last index node
         *
         * @param index reverse order number
         */
        public Node lastNode(int index) {
            int size = size();
            if (index <= 0 || index > size) {
                return null;
            }

            Node temp = nodes.next;
            for (int i = 0; i < size - index; i++) {
                temp = temp.next;
            }
            return temp;
        }

        /**
         * reverse list
         */
        public SLL reverse() {
            SLL sll = new SLL();
            // node size is 0 or 1
            if (nodes.next == null || nodes.next.next == null) {
                return sll;
            }

            Node current = nodes.next;
            // current node.next
            Node next;
            Node reverseNodes = new Node();
            while (current != null) {
                next = current.next;
                current.next = reverseNodes.next;
                reverseNodes.next = current;
                // current node move
                current = next;
            }
            sll.nodes = reverseNodes;
            return sll;
        }

        /**
         * 使用栈进行反转
         */
        public void reversePrintByStack() {
            if (nodes.next == null) {
                return;
            }

            Stack<Node> stack = new Stack<>();
            Node temp = nodes.next;
            while (temp != null) {
                stack.push(temp);
                temp = temp.next;
            }

            while (stack.size() > 0) {
                System.out.println(stack.pop());
            }
        }

        public void list() {
            // skip the first null node
            Node temp = nodes.next;
            while (temp != null) {
                System.out.println(temp);
                temp = temp.next;
            }
        }
    }

    /**
     * data node for linked list
     */
    @Setter
    @Getter
    @ToString
    static class Node {
        /**
         * current node number
         */
        Integer no;

        String key;

        Object val;

        /**
         * next node.
         * It will be the last node when this <code>next</code> equals <code>null</code>
         */
        @ToString.Exclude
        Node next;

        public Node() {
            this.no = 0;
            this.key = "";
            this.val = "";
        }

        public Node(Integer no, String key, Object val) {
            this.no = no;
            this.key = key;
            this.val = val;
        }
    }

}

